package randomthoughts.dp;

/**
 * @author tongchen
 * @create 2023-05-09 23:23
 */
public class ReverseSubString {

    //回文子串问题
    //定义dp数组:dp[i][j] [i,j]范围内的字符串是否为回文子串
    //递推顺序：1.j-i<=1 if(i==j) return true j-i 2.j-i>1 return dp[i+1][j-1]
    public int countSubstrings(String s) {
        int res=0;
        //创建dp数组
        boolean[][]dp=new boolean[s.length()][s.length()];
        //进行遍历
        for(int i=s.length()-1;i>=0;--i){
            for(int j=i;j<s.length();++j){
                if(s.charAt(i)==s.charAt(j)){
                    if(j-i<=1){
                        dp[i][j]= true;
                        res++;
                    }else{
                        if(dp[i+1][j-1]==true){
                            dp[i][j]= true;
                            res++;
                        }
                    }
                }
            }
        }
        return res;
    }
}
